package C50;

import C004.SelectBubbleInsert;

/**
 * ClassName: C07
 * Package: C50
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/28 18:44
 * @Version 1.0
 * @Since 1.0
 */
public class C07 {
    public static void main(String[] args) {
        int[] arr = {1,2,0};
        System.out.println(firstMissingPositive(arr));
    }


    public static int firstMissingPositive(int[] nums) {
        int l = 0, r = nums.length;
        while(l < r) {
            if(nums[l] == l + 1) {
                l ++;
            }else if(nums[l] < l + 1 || nums[l] > nums.length || nums[nums[l] - 1] == nums[l]) {
                // 垃圾值
                swap(nums, l, --r);
            } else {
                swap(nums, l, nums[l] - 1);
            }
        }
        return l + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
